Homework 10 - Naiara Alonso Montes¶

Exercise 1¶

The NN algorithm is a greedy algorithm, so the best solution is not always found. I created a NN search for the TSP problem, and after a path is found by the NN, I optimize it using 2-opt algorithm, which "swap" two edges, until there is no better solution.

In terms of complexity, it is not the best if the NN path is one of the worst possibles, but for a small dataset, it improves efficiency, as the 2-opt does not need to iterate through all the graph.

Initial path length: 5333.83
Optimized path length: 5090.93
Optimized path: ['p1', 'p8', 'p18', 'p3', 'p16', 'p6', 'p29', 'p5', 'p10', 'p4', 'p24', 'p2', 'p12', 'p14', 'p27', 'p26', 'p25', 'p19', 'p23', 'p30', 'p28', 'p15', 'p9', 'p21', 'p7', 'p17', 'p13', 'p20', 'p22', 'p11']

tsp_optimization.gif

Exercise 2¶

I did a bechmark measuring the time for NN alone, Simulated Annealing with NN start and Simulated Annealing with random start. Here are the time result

Here are the results for 30, 100, 200 and 1000.

Start Method Distance Time (seconds)
Random 4773.54 0.20
NN 5333.83 0.00
SA (NN Start) 4982.03 0.23
Random 11166.82 1.54
NN 8794.19 0.01
SA (NN Start) 8794.19 1.93
Random 18466.65 5.70
NN 13253.72 0.06
SA (NN Start) 13253.72 6.97
Random 81700.44 152.59
NN 30592.35 10.05
SA (NN Start) 30592.35 186.43

For 30 points, the NN and Simulated Annealing got the same results. For larger sets, they perform equally.

Here are the graphs for 100 points: sa_random_hw10_tsp_points_data_0100.txt.png

nn_hw10_tsp_points_data_0100.txt.png

sa_nn_hw10_tsp_points_data_0100.txt.png

Exercise 3¶

After 5 LONG HOURS of running my code, I only managed to finde the best paths for the 30 and 100 points, 200 points was still running when I lost the hope in my program. If it works for 30 and 100, it must work for other sizes.

Here are the results that I obtained:

TSP tour (node order) for ../hw10_tsp_points_data_0030.txt:
[0, 7, 17, 2, 15, 16, 12, 19, 21, 13, 11, 10, 5, 28, 4, 9, 3, 23, 1, 26, 25, 24, 22, 18, 29, 27, 14, 8, 6, 20]
Best total distance: 4978.884755224435
TSP tour (node order) for ../hw10_tsp_points_data_0100.txt:
[0, 7, 44, 79, 20, 89, 53, 6, 62, 80, 38, 12, 16, 72, 92, 5, 74, 49, 33, 10, 11, 97, 61, 23, 31, 60, 1, 13, 90, 21, 68, 19, 70, 87, 47, 95, 71, 55, 82, 59, 64, 93, 65, 8, 14, 50, 37, 58, 27, 56, 73, 48, 54, 39, 29, 96, 94, 35, 86, 22, 18, 81, 57, 46, 52, 91, 77, 83, 99, 85, 24, 84, 25, 42, 26, 66, 43, 51, 40, 78, 88, 3, 30, 9, 4, 98, 45, 28, 67, 36, 15, 41, 2, 75, 69, 63, 34, 17, 76, 32]
Best total distance: 8190.663183174403

best_30.png

best_100.png

Exercise 4¶

tartu.jpg

tartu_shuffled.png

tartu_ordered.png

What the code does is apply the Euclidean Distance (which is the base of the NN) to evaluate which row is most similar to the actual row. This process it is repeated until there are no left rows to train.

  • Is it sorted? Yes
  • Is it well sorted? Obviously not, but I am happy with the solution.

Exercise 5¶

Providing that we have unlimited resources and that our code is perfect for the TSP, the best and optimal solution for restoring the image will be ussing this approach. Of course, this is really good to be true, where computing capacity is limited. TSP will be the best option if our image is small enough so the overhead due to the computing is something reasonable.

On the other hand, we will have to accept that we have limited resources and that it can be hard to have always the best solution.

Nearest Neighbours is a greedy approach that under some circumpstances it might find the best solution with less computing time.

For the two-way Nearest Neighbour, it will have less problems when there are more than one similar rows and be less likely to have problems with noise (random variations but at the end the rows are not related).

Based on that, I would recommend to work with two-way Nearest Neighbours.

In [ ]:
!jupyter nbconvert --to html HW10.ipynb